package algorithm.leetcode.I1to100;

public class Q41 {

    public int firstMissingPositive(int[] nums) {

        // 如果是不是正的,全部变成nums.length+1
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= 0) nums[i] = nums.length+1;
        }

        // 当前元素是正,并且在1~nums.length之间,标记对应的索引对应的数字
        // 如果nums[i]没被标记并且在1~N之间,将nums[i]这个位置的数字变成负的
        for (int i = 0; i < nums.length; i++) {
            int abs = Math.abs(nums[i])-1;
            if (abs < nums.length) {
                nums[abs] = -Math.abs(nums[abs]);
            }
        }

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= 0) return i+1;
        }
        return nums.length+1;
    }

    public static void main(String[] args) {
        Q41 q41 = new Q41();
        int[] ints = new int[]{1,2,0};
        System.out.println(q41.firstMissingPositive(ints));
    }
}
